package com.kx.demo.jdk.collection;

import java.util.Collection;
import java.util.Deque;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

/**
 * @author kx
 * @date 2020/4/11
 */
public class KxLinkedList<E> implements List<E> {

    transient int size = 0;
    transient Node<E> first;
    transient Node<E> last;

    public KxLinkedList() {
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size != 0;
    }

    @Override
    public boolean contains(Object o) {
        return false;
    }

    @Override
    public Iterator<E> iterator() {
        return null;
    }

    @Override
    public Object[] toArray() {
        return new Object[0];
    }

    @Override
    public <T> T[] toArray(T[] a) {
        return null;
    }

    @Override
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    private void linkLast(E e) {
        Node<E> l = last;
        Node<E> newNode = new Node<>(e, last, null);
        last = newNode;
        if (l == null) {
            first = newNode;
        } else {
            l.next = newNode;
        }
        size++;
    }

    private void linkBefore(E e) {
        Node<E> newNode = new Node<>(e, null, first);
        if (first == null) {
            last = newNode;
        } else {
            first.prev = newNode;
            first = newNode;
        }
        size++;
    }

    @Override
    public boolean remove(Object o) {
        if (size == 0 || o == null) {
            return false;
        }
        Node<E> tmpNode = first;
        while (tmpNode != null) {
            if (o.equals(tmpNode.item)) {
                unLink(tmpNode);
                return true;
            } else {
                tmpNode = tmpNode.next;
            }
        }
        return false;
    }

    private E unLink(Node<E> tmpNode) {
        if (tmpNode == null) {
            return null;
        }
        E element = tmpNode.item;
        Node<E> prev = tmpNode.prev;
        Node<E> next = tmpNode.next;

        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            tmpNode.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            tmpNode.next = null;
        }

        tmpNode.item = null;
        size--;
        return element;
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        return false;
    }

    @Override
    public boolean addAll(Collection<? extends E> c) {
        return false;
    }

    @Override
    public boolean addAll(int index, Collection<? extends E> c) {
        return false;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        return false;
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        return false;
    }

    @Override
    public void clear() {

    }

    @Override
    public E get(int index) {
        Node<E> target = index(index);

        return target != null ? target.item : null;
    }

    private void ensureIndexInternal(int index) {
        if (index >= size || index < 0) {
            throw new IndexOutOfBoundsException();
        }
    }


    private Node<E> index(int index) {
        ensureIndexInternal(index);
        if (size == 0) {
            return null;
        }

        // 从头部遍历
        Node<E> tmpNode = first;
        if (index < (size >> 1)) {
            for (int i = 0; i < index; i++) {
                tmpNode = tmpNode.next;
            }

        } else {
            // 从尾部遍历
            tmpNode = last;
            for (int i = size - 1; i > index; i--) {
                tmpNode = tmpNode.prev;
            }
        }
        return tmpNode;
    }

    @Override
    public E set(int index, E element) {
        ensureIndexInternal(index);
        if (size == 0) {
            return null;
        }
        Node<E> target = index(index);
        E oldItem = target.item;
        target.item = element;
        return oldItem;
    }

    @Override
    public void add(int index, E element) {
        ensureIndexInternal(index);
        if (index == size) {
            linkLast(element);
        } else {
            linkBefore(element, index(index));
        }
    }

    private void linkBefore(E element, Node<E> index) {
        Node<E> prev = index.prev;
        Node<E> newNode = new Node<>(element, prev, index);
        index.prev = newNode;
        if (prev == null) {
            first = newNode;
        } else {
            newNode.prev = prev;
        }
        size++;
    }

    @Override
    public E remove(int index) {
        return unLink(index(index));
    }

    private int index(Object o) {
        if (o == null) {
            return -1;
        }
        Node<E> tmpNode = first;
        for (int i = 0; i < size; i++) {
            if (o.equals(tmpNode.item)) {
                return i;
            }
            tmpNode = tmpNode.next;
        }
        return -1;
    }

    private int indexLast(Object o) {
        if (o == null) {
            return -1;
        }
        int index = -1;
        Node<E> tmpNode = first;
        for (int i = 0; i < size; i++) {
            if (o.equals(tmpNode.item)) {
                index = i;
            }
            tmpNode = tmpNode.next;
        }
        return index;
    }

    @Override
    public int indexOf(Object o) {
        return index(o);
    }

    @Override
    public int lastIndexOf(Object o) {
        return indexLast(o);
    }

    @Override
    public ListIterator<E> listIterator() {
        return null;
    }

    @Override
    public ListIterator<E> listIterator(int index) {
        return null;
    }

    @Override
    public List<E> subList(int fromIndex, int toIndex) {
        return null;
    }

    private static class Node<E> {

        private E item;
        private Node<E> prev;
        private Node<E> next;

        public Node(E item, Node<E> prev, Node<E> next) {
            this.item = item;
            this.prev = prev;
            this.next = next;
        }
    }

    @Override
    public String toString() {
        if (size == 0)
            return "[]";

        StringBuilder sb = new StringBuilder();
        sb.append('[');
        Node<E> tmpNode = first;
        for (int i = 0; i < size - 1; i++) {
            sb.append(tmpNode.item);
            sb.append(", ");
            tmpNode = tmpNode.next;
        }
        sb.append(tmpNode.item);
        return sb.append(']').toString();
    }
}
